package com.leetcode.partition2;

import java.util.*;

/**
 * @author `RKC`
 * @date 2021/11/9 20:16
 */
public class LC127单词接龙 {

    public static int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> wordDict = new HashSet<>(wordList);
        //最终的单词都没在字典中，没有任何必要进行寻找
        if (!wordDict.contains(endWord)) return 0;
        Map<Integer, Set<Character>> indexToChars = new HashMap<>(beginWord.length());
        for (int i = 0; i < beginWord.length(); i++) {
            Set<Character> chars = new HashSet<>(beginWord.length());
            for (String word : wordList) {
                chars.add(word.charAt(i));
            }
            indexToChars.put(i, chars);
        }
        int ans = bfs(beginWord, endWord, wordDict, indexToChars);
        return ans == -1 ? 0 : ans + 1;
//        return bfs(beginWord, endWord, wordDict, indexToChars);
    }

    public static void main(String[] args) {
        //"hit" -> "hot" -> "dot" -> "dog" -> cog"
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        String beginWord = "hit", endWord = "cog";
        System.out.println(ladderLength(beginWord, endWord, wordList));
    }

    private static int bfs(String beginWord, String endWord, Set<String> wordDict, Map<Integer, Set<Character>> indexToChars) {
        //创建正向和反向队列，正向搜索endWord，反向搜索beginWord
        LinkedList<String> queue1 = new LinkedList<>(), queue2 = new LinkedList<>();
        //分别记录正向队列和反向队列对应字符距离起点的距离
        Map<String, Integer> map1 = new HashMap<>(), map2 = new HashMap<>();
        queue1.addLast(beginWord);
        map1.put(beginWord, 0);
        queue2.addLast(endWord);
        map2.put(endWord, 0);
        //只要两个队列都不为空才有必要继续搜索，如果任意一个队列为空，就说明不可达，没有任何的搜索必要
        while (!queue1.isEmpty() && !queue2.isEmpty()) {
            int ans = -1;
            //尽量平衡查找
            if (queue1.size() <= queue2.size()) {
                ans = search(queue1, map1, map2, wordDict, indexToChars);
            } else {
                ans = search(queue2, map2, map1, wordDict, indexToChars);
            }
            if (ans != -1) return ans;
        }
        return -1;
    }

    private static int search(LinkedList<String> queue, Map<String, Integer> curMap, Map<String, Integer> otherMap, Set<String> wordDict
            , Map<Integer, Set<Character>> indexToChars) {
        String s = queue.pollFirst();
        int dis = curMap.get(s);
        for (int i = 0; i < s.length(); i++) {
            Set<Character> charSet = indexToChars.get(i);
            for (Character ch : charSet) {
                String next = s.substring(0, i) + ch + s.substring(i + 1);
                //当前字符串不在字典中或者当前字符串在当前方向上已经出现过，就进行跳过
                if (!wordDict.contains(next) || curMap.containsKey(next)) continue;
                //如果在另一个方向过来的路径找到了对应的字符，说明可以组成最短路
                if (otherMap.containsKey(next)) {
                    return otherMap.get(next) + dis + 1;
                }
                //加入队列，继续搜索
                queue.addLast(next);
                curMap.put(next, dis + 1);
            }
        }
        return -1;
    }

    private static int bfs0(String beginWord, String endWord, Set<String> wordDict, Map<Integer, Set<Character>> indexToChars) {
        //[字符串, 转换几次得到]，最小堆保证了最短路径
        PriorityQueue<String[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(o -> Integer.parseInt(o[1])));
        Set<String> visited = new HashSet<>();
        //初始化，每个位置的字符都变化一次，且把在字典中出现过的单词加入优先队列
        for (int i = 0; i < beginWord.length(); i++) {
            Set<Character> charSet = indexToChars.get(i);
            for (Character ch : charSet) {
                String next = beginWord.substring(0, i) + ch + beginWord.substring(i + 1);
                if (wordDict.contains(next)) {
                    priorityQueue.offer(new String[]{next, "2"});
                    visited.add(next);
                }
            }
        }
        while (!priorityQueue.isEmpty()) {
            String[] cur = priorityQueue.poll();
            String curStr = cur[0];
            int times = Integer.parseInt(cur[1]);
            //找到最终答案
            if (curStr.equals(endWord)) return times;
            for (int i = 0; i < curStr.length(); i++) {
                Set<Character> charSet = indexToChars.get(i);
                for (Character ch : charSet) {
                    String next = curStr.substring(0, i) + ch + curStr.substring(i + 1);
                    //不能重复访问，避免成环，且新生成的单词要在字典中存在
                    if (!visited.contains(next) && wordDict.contains(next)) {
                        priorityQueue.offer(new String[]{next, String.valueOf(times + 1)});
                        visited.add(next);
                    }
                }
            }
        }
        return 0;
    }
}
